#include <iostream>
#include <list>
#include <string.h>
using namespace std;

void printVec(int vec[], int m)
{
    for (int i = 0; i < m; i++)
    {
        cout << vec[i] << "-";
    }
    cout << endl;
}
// 合并有序数组
class Solution
{
public:
    void merge(int A[], int m, int B[], int n)
    {
        bool s = false; // 升序
        if (m >= 2)
        {
            if (A[0] > A[1])
            {
                s = true; // 降序
            }
        }
        else
        {
            if (n >= 2 && B[0] > B[1])
                s = true;
        }
        list<int> vec;
        if (s)
        {
            for (; m >= 0 && n >= 0;)
            {
                if (B[n] >= A[m]) {
                    vec.push_back(B[n--]);
                } else {
                    vec.push_back(A[m--]);
                }
            }
            if (m >= 0) {
                for(;m >= 0;)vec.push_back(A[m--]);
            } else {
                for(;n >= 0;)vec.push_back(B[n--]);
            }
        }
        else
        {
            int i = 0, j = 0;
            for (; i < m && j < n;)
            {
                if (B[j] <= A[i]) {
                    vec.push_back(B[j++]);
                } else {
                    vec.push_back(A[i++]);
                }
            }
            if (i >= m) {
                for(;j < n;)vec.push_back(B[j++]);
            } else {
                for(;i < m;)vec.push_back(A[i++]);
            }
        }
        for (int i = 0; i < m + n; i++) {
            int p = vec.front();
            A[i] = p;
            vec.pop_front();
        }
    }
};

int main()
{
    Solution s;
    int p1[100] = {1, 2, 5, 9, 45};
    int p2[4] = {5, 8, 12, 22};
    s.merge(p1, 5, p2, 4);
    printVec(p1, 9);
    return 0;
}